package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KSlidingWindow;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. 无重复字符的最长子串
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters
 * TODO 加练
 */
public class LC3_LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        String s = "abcabcbb";
        int len = new Solution().lengthOfLongestSubstring(s);
        System.out.println(len);
    }

    /**
     *
     */
    @XOptimal
    @KSlidingWindow(KSlidingWindow.WindowType.VARIABLE_LENGTH)
    static
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s.length() == 0) {
                return 0;
            }
            int[] counts = new int[256];
            int j = -1, longest = 1;
            for (int i = 0; i < s.length(); i++) {
                counts[s.charAt(i)]++;
                while (hasGreaterThan1(counts)){
                    j++;
                    counts[s.charAt(j)]--;
                }
                longest = Math.max(i - j, longest);
            }
            return longest;
        }

        private boolean hasGreaterThan1(int[] counts) {
            for (int count : counts) {
                if(count > 1) {
                    return true;
                }
            }
            return false;
        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public int lengthOfLongestSubstring(String s) {
            char[] chars = s.toCharArray();
            int n = s.length(), left = 0, res = 0;
            int[] counter = new int[128];
            for (int right = 0; right < n; right++) {
                char c = chars[right];
                counter[c]++;
                while (counter[c] > 1) {
                    counter[chars[left]]--;
                    left++;
                }
                res = Math.max(res, right - left + 1);
            }
            return res;
        }
    }
}
